package q213_rob;

/**
 * 同样是动态规划问题
 * 我们直接考虑198中的方法抽取出来
 * 其实该题我们无非要考虑两种情况而已，链接成环的地方是n号和1号房间
 * 我们只能选择
 * 1 不偷n号房 那么获得的就是剩下房间的最大值
 * 2 不偷1号房 同样的也是剩下房间得到的最大值
 * 只需要用打家劫舍的思路把两种情况都执行一边即可
 */
public class Solution {

    public int rob(int[] nums) {
        if (nums.length <= 2) {
            return nums.length == 1 ? nums[0] : Math.max(nums[1],nums[0]);
        }
        return Math.max(robPart(nums, 0), robPart(nums, 1));
    }

    public int robPart(int[] nums, int index) {
        // 注意要更改的地方
        // 1 robs数组的长度
        // 2 robs数组0和1号位置的初始值
        // 3 robs[i]推导时有一项变为nums[i + index]

        int[] robs = new int[nums.length - 1];

        robs[0] = nums[index];
        robs[1] = Math.max(nums[index + 1], nums[index]);

        for (int i = 2; i < nums.length - 1; i++) {
            robs[i] = Math.max(robs[i - 2] + nums[i + index], robs[i - 1]);
        }

        return robs[nums.length - 2];
    }
}
